def longest_common_subsequence(X, Y):
    """
    使用动态规划求解最长公共子序列
    返回LCS的长度和序列本身
    """
    m, n = len(X), len(Y)

    # 创建DP表，dp[i][j]表示X[0:i]和Y[0:j]的LCS长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 回溯构造LCS
    lcs_sequence = construct_lcs(X, Y, dp)

    return dp[m][n], lcs_sequence


def construct_lcs(X, Y, dp):
    """
    回溯构造最长公共子序列
    """
    i, j = len(X), len(Y)
    lcs = []

    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))


def print_dp_table(X, Y, dp):
    """
    打印DP表
    """
    print("\nDP表:")
    print("    ", end="")
    for char in " " + Y:
        print(f"{char:>3}", end="")
    print()

    for i in range(len(dp)):
        if i == 0:
            print("  ", end="")
        else:
            print(f"{X[i - 1]:>2}", end="")
        for j in range(len(dp[i])):
            print(f"{dp[i][j]:>3}", end="")
        print()


# 测试最长公共子序列
def test_lcs():
    X = "ABCBDAB"
    Y = "BDCABA"

    print("最长公共子序列问题:")
    print(f"序列 X: {X}")
    print(f"序列 Y: {Y}")

    length, lcs_seq = longest_common_subsequence(X, Y)

    print(f"\n最长公共子序列长度: {length}")
    print(f"最长公共子序列: {lcs_seq}")

    # 打印DP表
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 重新填充DP表用于显示
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    print_dp_table(X, Y, dp)


# 运行测试
test_lcs()
